package code;

import java.util.ArrayList;
import java.util.List;

public class Code210 {
	/*
	 * top排序
	 */
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int i;
        int[] ans=new int[numCourses];
        List<List<Integer>> inEdge=new ArrayList<List<Integer>>();
        List<List<Integer>> outEdge=new ArrayList<List<Integer>>();
        
        for(i=0;i<numCourses;i++){
        	inEdge.add(new ArrayList<Integer>());
        	outEdge.add(new ArrayList<Integer>());
        }
        
        for(i=0;i<prerequisites.length;i++){
        	int a=prerequisites[i][0];
        	int b=prerequisites[i][1];
        	inEdge.get(a).add(b);
        	outEdge.get(b).add(a);
        }
        int cnt=0;
        boolean[] vis=new boolean[numCourses];
        
        while(true){
        	List<Integer> list=new ArrayList<Integer>();
        	for(i=0;i<numCourses;i++){
        		//入度为0
        		if(!vis[i] && inEdge.get(i).size()==0){
        			list.add(i);
        			ans[cnt++]=i;
        			vis[i]=true;
        		}
        	}
        	if(cnt==numCourses)
        		break;
        	if(list.size()==0)
        		return new int[0];
        	/*
        	 * 将入度为0的点删掉
        	 */
        	for(i=0;i<list.size();i++){
        		int x=list.get(i);
        		for(int j=0;j<outEdge.get(x).size();j++){
        			int y=outEdge.get(x).get(j);
        			for(int k=0;k<inEdge.get(y).size();k++){
        				if(inEdge.get(y).get(k)==x)
        				{
        					inEdge.get(y).remove(k);
        					break;
        				}
        			}
        		}
        	}
        }
        return ans;
    }
    /*
     * 207,检查是否不能top排序的
     */
    public boolean canFinish(int numCourses, int[][] prerequisites){
        int i;
        int[] ans=new int[numCourses];
        List<List<Integer>> inEdge=new ArrayList<List<Integer>>();
        List<List<Integer>> outEdge=new ArrayList<List<Integer>>();
        
        for(i=0;i<numCourses;i++){
        	inEdge.add(new ArrayList<Integer>());
        	outEdge.add(new ArrayList<Integer>());
        }
        
        for(i=0;i<prerequisites.length;i++){
        	int a=prerequisites[i][0];
        	int b=prerequisites[i][1];
        	inEdge.get(a).add(b);
        	outEdge.get(b).add(a);
        }
        int cnt=0;
        boolean[] vis=new boolean[numCourses];
        
        while(true){
        	List<Integer> list=new ArrayList<Integer>();
        	for(i=0;i<numCourses;i++){
        		//入度为0
        		if(!vis[i] && inEdge.get(i).size()==0){
        			list.add(i);
        			ans[cnt++]=i;
        			vis[i]=true;
        		}
        	}
        	if(cnt==numCourses)
        		break;
        	if(list.size()==0)
        		return false;
        	/*
        	 * 将入度为0的点删掉
        	 */
        	for(i=0;i<list.size();i++){
        		int x=list.get(i);
        		for(int j=0;j<outEdge.get(x).size();j++){
        			int y=outEdge.get(x).get(j);
        			for(int k=0;k<inEdge.get(y).size();k++){
        				if(inEdge.get(y).get(k)==x)
        				{
        					inEdge.get(y).remove(k);
        					break;
        				}
        			}
        		}
        	}
        }
        return true;
    }
    
    public static void main(String[] args){
    	int[][] p={{1,0},{2,0},{3,1},{3,2}};
    	new Code210().findOrder(4, p);
    }
}
